This invention relates to a failure analysis for a semiconductor integrated circuit device and, more particularly, to a failure analysis system, a method for managing estimated logic status and an information storage medium for storing programmed instructions of the method.
A method for managing estimated logic status is available for a failure analysis system for a sequential circuit disclosed, by way of example, in Japanese Patent Publication of Unexamined Application No. 8-146093. In the following description, term xe2x80x9ccombinational circuitxe2x80x9d expresses a combination of component circuits of an integrated circuit. The prior art failure analysis system backwardly traces a propagation path from a defective output toward an origin of trouble, and dynamically extracts combinational circuits possibly propagating the trouble. The prior art failure analysis system evaluates the extracted combinational circuits, and gives estimated logic status to the extracted combinational circuit. The logic status is given to not only signal lines but also all nodes in the extracted combinational circuit. Signal lines, gates and input/output nodes are examples of the node to be evaluated. The logic status is represented by more than two logic values, i.e., logic xe2x80x9c0xe2x80x9d, logic xe2x80x9c1xe2x80x9d, X which means xe2x80x9cdon""t carexe2x80x9d, Z which means high-impedance and U which means undefined. When the extracted combinational circuits are linked by using the logic status, the logical link is expected to guide the analyst to the origin of trouble.
An estimated linkage of logic status of each combinational circuit is managed by using the prior art method for managing estimated logic status. Pieces of status information representative of the logic status are registered, retrieved and selectively canceled, and are formed into a tree-like index structure. A large scale integration has a large number of combinational circuits, and more than one logic value is possibly given to each combinational circuit. For this reason, the tree-like index structure for the large scale integration is huge, and the relation between the pieces of status information is less clear to an analyst.
FIG. 1 illustrates a prior art failure analysis system for the estimated logic status. The prior art failure analysis system is broken down into an input-output unit 1, a data processing unit 2 and a memory unit 3. Input data is supplied from the outside through the input-output unit 1 to the data processing unit 2. The data processing unit 2 sequentially executes programmed instructions for a failure analysis, stores pieces of status information for a combinational circuit and a tree-like index structure representative of the logic status in the memory unit 3, and delivers data to be required through the input-output unit 1b. 
The input-output unit 1 includes a data input unit 1a and a data output unit 1b. The input unit 1a is a keyboard and a data interface to a diagnostic system (not shown). The output unit 1b is a printer and a data interface to the diagnostic system. The memory unit 3 includes a memory 3a for data information representative of the logic status of combinational circuits and a memory 3b for storing the tree-like index structure. Each of the pieces of status information represents the logic status at a node in a combinational circuit, and the logic status is labeled with an index. A logic value is given to the logic status, and the logic values are logic xe2x80x9c1xe2x80x9d, logic xe2x80x9c0xe2x80x9d, X which means xe2x80x9cdon""t carexe2x80x9d, Z which means high-impedance and U which means undefined. The node means a signal line, a gate, a gate terminal and an input/output terminal of a component circuit. On the other hand, the tree-like index structure is stored in the memory unit 3b. The tree-like index structure is built for each combinational circuit, and represents a linkage of logic status between the nodes.
The data processing unit 2 includes an instruction analyzer 2a connected to a program memory (not shown), an index marker 2b, a condition analyzer 2c for retrieving conditions and a condition analyzer 2d for deleting conditions. The index marker 2b, the condition analyzer 2c and the condition analyzer 2d are respectively accompanied with a register 2e, a retriever 2f and a deleting means 2g. 
The instruction analyzer 2a analyzes an instruction supplied from the input unit 1a, and the data processing unit selectively branches the control to a data registration, a data retrieval and a data deletion. In other words, the control sequence is transferred from the instruction analyzer 2a to the index marker 2b, the retrieving conduction analyzer 2c or the condition analyzer 2d. 
The index marker 2b adds an index to the logic status given to a node or a group of nodes to be registered, and transfers the piece of status information representative of the logic status labeled with the index to the register 2e. The index is representative of both of a name of nodes in the combinational circuit and a relation between the nodes. If nodes are branched from a node, the nodes respectively have sub-indexes branched from an index given t o the node. A name is given to each node, and the name of node is also stored so as to make the linkage clear. The register 2e assorts the pieces of status information by the index, and stores the pieces of status information together with the names of the associated nodes. Moreover, the register 2e builds the pieces of status information into a tree-like index structure, and stores the tree-like index structure in the memory unit 3b. While the register 2e is building the pieces of status information into the tree-like index structure, the sub-indexes are located under the index. Thus, lower-level indexes are branched from an upper-level index, and all the indexes are built into the tree-like index structure.
The condition analyzer 2c determines search conditions for a data retrieving to be requested, and supplies the search conditions to the retriever 2f. The retriever 2f searches the memory units 3a/3b for a piece or pieces of status information satisfying the search conditions, and supplies the search result to the output unit 1b. 
The condition analyzer 2d determines search conditions for a deletion of a piece of or pieces of status information from the contents of the memory units 3a/3b, and supplies the search conditions to the deleting means 2g. The deleting means 2g deletes a piece of pieces of status information satisfying the search conditions from the contents of the memory units 3a/3b. 
FIG. 2 illustrates the control sequence achieved by the prior art failure analysis system, and FIG. 3 illustrates a tree-like index structure built by the prior art failure analysis system. The tree-like index structure is finally achieved through repetition of the control sequence shown in FIG. 2. F1 to F16 are indicative of the names of nodes incorporated in a combinational circuit, and numeral xe2x80x9c0xe2x80x9d in a circle to numeral xe2x80x9c15xe2x80x9d in a circle are representative of the indexes each given to a group of nodes such as (F1, F2). FIG. 4 shows a logic path from the index xe2x80x9c0xe2x80x9d through the indexes xe2x80x9c1xe2x80x9d and xe2x80x9c3xe2x80x9d to the index xe2x80x9c6xe2x80x9d and the index xe2x80x9c8xe2x80x9d in the tree-like index structure, and FIG. 5 shows another logic path from the index xe2x80x9c0xe2x80x9d through the indexes xe2x80x9c1xe2x80x9d and xe2x80x9c4xe2x80x9d to the index xe2x80x9c10xe2x80x9d and the index xe2x80x9c12xe2x80x9d in the tree-like index structure. The logic paths are determined through the execution of the program sequence shown in FIG. 2.
The prior art control sequence is firstly described hereinbelow. Assuming now that a programmed instruction code is supplied from the input unit 1a to the instruction analyzer 2a, the instruction analyzer 2a sequentially checks the instruction code at steps SP1/SP2/SP3, and transfers the control to the index marker 2b, the condition analyzer 2c and the condition analyzer 2d. In detail, the instruction analyzer 2a firstly checks the programmed instruction to see whether or not the programmed instruction requests the registration as by step SP1. If the answer at step SP1 is given affirmative, the instruction analyzer 2a transfers the control to the index marker 2b, and the index marker 2b starts the registration as described hereinlater in detail.
On the other hand, if the answer at step SP1 is given negative, the instruction analyzer 2a checks the programmed instruction to see whether or not the programmed instruction re(quests the retrieval as by step SP2. If the answer at step SP2 is given affirmative, the instruction analyzer 2a transfers the control to the condition analyzer 2c, and the condition analyzer 2c cooperates with the retriever 2f for the retrieval of data as described hereinlater.
On the other hand, if the answer at step SP2 is given negative, the instruction analyzer 2a checks the programmed instruction to see whether or not the programmed instruction requests a deletion. If the answer at step SP3 is given affirmative, the instruction analyzer 2a transfers the control to the condition analyzer 2c, and the condition analyzer 2d cooperates with the deleting means 2g for deleting data as described hereinlater.
When the instruction analyzer 2a determines the programmed instruction to request the registration, the index marker 2b adds an index to the logic status for the purpose of data discrimination as by step SP4. A group of the names assigned the nodes and logic value assigned thereto are incorporated in a piece of status information representative of the logic status, and a single index is given to the logic status. It is assumed that an upper-level index had been known. The logic status was estimated for the lower-level index or the sub-index on the basis of the pieces of status information for the upper-level index. The piece of status information is supplied to the register 2e together with the index, and the register 2e stores the pieces of status information and the index in the memory unit 3a as by step SP5. If the index is a sub-index, the linkage between the index and the sub-index is also stored in the memory unit 3a. 
If the instruction analyzer 2a determines the given programmed instruction to request a data retrieval, the condition analyzer 2c analyzes given data, and determines conditions for a search as by step SP6. The search conditions are transferred from the condition analyzer 2c to the retriever 2f, and the retriever 2f searches the memory units 3a/3b for a piece of status information satisfying the search conditions as by step SP7. The result of the retrieval is output through the output unit 1b as by step SP8.
If the instruction analyzer 2a determines the given programmed instruction to request a deletion, the condition analyzer 2d analyzes given data, and determines conditions for a search. The search conditions are transferred from the condition analyzer 2d to the deleting means 2g, and the deleting means 2g deletes a piece of status information satisfying the search conditions together with the given index.
Description is hereinbelow made on part of the work of building the tree-like index structure with reference to FIGS. 4/5. Circuits 4a/4b/4c/4d form a combinational circuit (see FIG. 4), and circuits 4a/4b/4c/4e form another combinational circuit (see FIG. 5). Unexpected output signals are assumed to appear at the terminals F1 and F2. The terminal F1/F2 is hereinbelow referred to as xe2x80x9cdefective terminalxe2x80x9d. Index xe2x80x9c0xe2x80x9d was assigned to the defective terminals F1/F2, and a piece of status information at the defective terminals F1/F2 and the index xe2x80x9c0xe2x80x9d have been already stored in the memory units 3a/3b. 
A programmed instruction is representative of a request for the retrieval, and is supplied from the input unit 1a to the instruction analyzer 2a upon completion of step SP2. The instruction analyzer 2a transfers the programmed instruction to the condition analyzer 2c, and the condition analyzer 2c determines search conditions to be a defective terminals not estimated yet at step SP6. The retriever 2f searches the memory units 3a/3b for the piece of status information satisfying the search conditions at step SP7. The retriever 2f finds the piece of status information representative of the terminals F1/F2 assigned index xe2x80x9c0xe2x80x9d. The retriever 2f transfers the search result indicting the defective terminals F1/F2 to the output unit 1b, and the output unit 1b outputs a search report at step SP8.
The prior art failure analysis system selects the circuit 4a on the basis of the search report for the defective terminal F1/F2 assigned index xe2x80x9c0xe2x80x9d, and estimates the logic status of the circuit 4a. Then, two kinds of logic status are determined. One of them is representative of a failure propagation path from the terminal F3 to the terminals F1/F2, and the other is representative of another failure propagation path from the terminal F4 to the terminals F1/F2 (see FIG. 3).
The prior art failure analysis system instructs the data processing unit 2 to register pieces of status information representative of the two kinds of logic status. The instruction analyzer 2a determines the given instruction to request a registration. The control is transferred to the index marker 2b. The index marker gives index xe2x80x9c1xe2x80x9d and index xe2x80x9c2xe2x80x9d to the pieces of status information (see FIG. 3) at step SP4. Index xe2x80x9c1xe2x80x9d and xe2x80x9c2xe2x80x9d are respectively assigned to the pieces of status information representative of the failure propagation path from the terminal F3 to the terminals F1/F2 and the logic status representative of the failure propagation path from the terminal F4 to the terminals F1/F2. Thereafter, the resister 2e stores the pieces of status information, i.e., the names of nodes or terminals and the logic value given to one kind of logic status and the names of nodes or terminals and the logic value given to the other kind of logic status in the memory units 3a, and inserts indexes xe2x80x9c1xe2x80x9d and xe2x80x9c2xe2x80x9d in the tree-like index structure stored in the memory unit 3b as lower-level indexes branched from index xe2x80x9c0xe2x80x9d at step SP5.
Upon completion of the registration, the prior art failure analysis system returns to step SPO, and searches the memory units 3a/3b for a terminal not estimated yet. The terminals F3/F4 are found, and the prior art failure analysis system repeats steps SP2, SP6, SP7 and SP8 for each of the terminals F3/F4.
The terminal F3 with index xe2x80x9c1xe2x80x9d relates to the circuit 4b, and the prior art failure analysis system extracts the circuit 4b from the combinational circuit. The prior art failure analysis system estimates the logic status of the circuit 4b. Two kinds of logic status are estimated. One of the two kinds-of logic status is representative of a failure propagation path from the terminal F3 to the terminals F5/F6 shown in FIG. 4, and the other kind of logic status is representative of a failure propagation path from the terminal F3 to the terminals F5/F7 shown in FIG. 5.
The prior art failure analysis system requests the data processing unit 2 to register the two kinds of logic status. The data processing unit 2 repeats the control sequence described hereinbefore, and stores the two kinds of logic status together with indexes xe2x80x9c3xe2x80x9d and xe2x80x9c4xe2x80x9d. Indexes xe2x80x9c3xe2x80x9d and xe2x80x9c4xe2x80x9d are inserted into the tree-like index structure as sub-indexes of index xe2x80x9c1xe2x80x9d.
The other terminal F4 has been assigned index xe2x80x9c2xe2x80x9d, and the prior art failure analysis system extracts a circuit from another combinational circuit, and estimates the logic status for the extracted circuit. Only one kind of logic status is obtained through the estimation, and is representative of a failure propagation path from the terminal F8 to the terminal F4 (see FIG. 3). The prior art failure analysis system instructs the data processing unit 2 to register the logic status for the extracted circuit. The data processing unit 2 repeats the above-described control sequence so as to store the logic status together with index xe2x80x9c5xe2x80x9d in the memory unit 3a and insert index xe2x80x9c5xe2x80x9d in the tree-like index structure in the memory unit 3b as a sub-index of index xe2x80x9c2xe2x80x9d.
Upon completion of the registration, the prior art failure analysis system instructs the condition analyzer 2c and the retriever 2f to search the memory 3 for terminals not estimated yet, and the retriever 2f finds the terminals F5/F6 of index xe2x80x9c3xe2x80x9d, the terminals F5/F7 of index xe2x80x9c4xe2x80x9d and the terminal F8 of index xe2x80x9c5xe2x80x9d. The prior art failure analysis system repeats the above-described control sequence for each of the terminals F5/F6, F5/F7 and F8.
In this way, the prior art failure analysis system repeats the program sequence shown in FIG. 2 for terminals not estimated yet, and, finally, completes the tree-like index structure shown in FIG. 3. The indexes are hierarchically built up into the tree-like index structure, and the links represent the relation between the upper-level indexes and the lower-level indexes. The indexes are associated with the defective terminals as shown.
The linkage shown in FIG. 4 is indicative of the following estimation. The defective terminal F3 is estimated on the basis of the logic status labeled with index xe2x80x9c1xe2x80x9d which has been determined from the defective terminals F1/F2 labeled with index xe2x80x9c0xe2x80x9d. The defective terminals F5/F6 are estimated on the basis of the logic status labeled with xe2x80x9c3xe2x80x9d for the terminal F3, and the defective terminals F9 and F11 are estimated on the basis of the logic status labeled with xe2x80x9c6xe2x80x9d for the defective terminal F5 and the logic status labeled with xe2x80x9c8xe2x80x9d for the defective terminal F6.
Similarly, the linkage shown in FIG. 5 is indicative of the following estimation. The defective terminal F3 is estimated as similar to the linkage shown in FIG. 4, and the defective terminals F5/F7 are estimated on the basis of the logic status labeled with xe2x80x9c4xe2x80x9d for the terminal F3, and the defective terminals F9 and F13 are estimated on the basis of the logic status labeled with xe2x80x9c10xe2x80x9d for the defective terminal F5 and the logic status labeled with xe2x80x9c12xe2x80x9d for the defective terminal F7.
An analyst acquires a piece of knowledge from the tree-like index structure that the estimation proceeds from index xe2x80x9c0xe2x80x9d through index xe2x80x9c1xe2x80x9d to index xe2x80x9c3xe2x80x9d. In other words, the tree-like index structure teaches the analyst the heretical relation between upper-level indexes and lower-level indexes. However, the tree-like index structure does not teach a logical relation between the indexes such as the AND relation or the OR relation. When two kinds of logic status are concurrently realized, they are in the AND relation. On the other hand, if two kinds of logic status are never concurrently realized, they are in the OR relation. Focusing attention on indexes xe2x80x9c3xe2x80x9d, xe2x80x9c6xe2x80x9d, xe2x80x9c7xe2x80x9d, xe2x80x9c8xe2x80x9d and xe2x80x9c9xe2x80x9d, by way of example, the tree-like index structure teaches that the four kinds of logic status xe2x80x9c6xe2x80x9d, xe2x80x9c7xe2x80x9d, xe2x80x9c8xe2x80x9d and xe2x80x9c9xe2x80x9d are estimated from the kind of logic status xe2x80x9c3xe2x80x9d. It is unknown that what kind of logic relation is found between the four kinds of logic status xe2x80x9c6xe2x80x9d, xe2x80x9c7xe2x80x9d, xe2x80x9c8xe2x80x9d and xe2x80x9c9xe2x80x9d. Because the logic status is not linked with any one of the two circuits relating to the terminals F5/F6. If all the relations between the indexes are registered, the analyst is to register a large number of combinations between the indexes, and the registration consumes a large, amount of time and labor. Thus, the analyst encounters a first problem in the prior art failure analysis system in that the tree-like index structure can not express any logical relation between the indexes.
The second problem is that the prior art failure analysis system can not specify the inside of the circuit, because the prior art failure analysis system does not select AND relations from the linkage.
The third problem is that the prior art failure analysis consumes a long time. As shown in FIG. 3, indexes xe2x80x9c6xe2x80x9d/xe2x80x9c10xe2x80x9d and xe2x80x9c7xe2x80x9d/xe2x80x9c11xe2x80x9d are branched from index xe2x80x9c3xe2x80x9d and index xe2x80x9c4xe2x80x9d, respectively. However, both indexes xe2x80x9c6xe2x80x9d and xe2x80x9c10xe2x80x9d are given to the logic status for the defective terminal F9. Similarly, both indexes xe2x80x9c7xe2x80x9d and xe2x80x9c11xe2x80x9d are given to the logic status for the defective terminal F10. This means that the estimation is repeated for the terminals F9/F10. The repetition increases the amount of estimation, and prolongs the time period for the failure analysis.
It is therefore an important object of the present invention to provide a failure analysis system, which is free from the problems inherent in the prior art failure analysis system.
It is also an important object of the present invention to provide a method of managing estimated logic status available for the failure analysis system.
It is also an important object of the present invention to provide an information storage medium for storing programmed instructions of the method.
The present inventor contemplated the first to third problems, and noticed that the source of those problems was that the prior art failure analysis system could not determine the logical relation between the kinds of logic status labeled with different indexes.
In accordance with one aspect of the present invention, there is provided a failure analysis system for a sequential circuit containing plural circuits comprising an index marker receiving pieces of status information each representative of a failure propagation path in one of the plural component circuits, and selectively labeling the pieces of status information with indexes in such as manner one of the pieces of status information is labeled with an index serving as an upper level index with respect to other or others of the pieces of status information closer to candidates of an failure origin than the one of the pieces of status information, a group organizer checking the indexes to see whether or not one or ones of the indexes are branched from another of the indexes serving as the upper level index, and giving a tag to the one or ones of the indexes when the one or ones of the indexes are branched from the another of the indexes, thereby selectively giving tags to the indexes, and a logical relation analyzer checking the indexes and the tags to see whether more than one piece of status information is established in an AND relation or an OR relation.
In accordance with another aspect of the present invention, there is provided a method of managing estimated logic status for a sequential circuit containing plural component circuits comprising the steps of a) acquiring pieces of status information each representative of a degradation of a failure propagation path in one of the plural component circuits and selectively labeled with indexes to be built in a tree-like index structure so as to indicate a relation of the failure propagation paths from candidates of a failure origin in the sequential circuit to a signal output port of the sequential circuit, one of the indexes given to one of the propagation paths closer to the signal output port serving as an upper level index in the tree-like index structure with respect to other or others of the indexes given to other or others of the propagation paths closer to the candidates and connected to the one of the propagation paths, b) checking the tree-like index structure to see whether one of or ones of the indexes are branched from another of the indexes serving as the upper level index so as to give a tag to the one or ones of the indexes when the one or ones of the indexes are branched from the another of indexes, thereby selectively giving tags to an index or a group of indexes incorporated in the tree-like index structure, c) checking the indexes to see whether or not the tag is shared between more than one of the indexes, and d) determining a logical relation between the more than one of the indexes to be an OR relation when the tag is shared and an AND relation when the tag is not shared.
In accordance with yet another aspect of the present invention, there is provided a information storage medium for storing a sequence of programmed instruction for a method of managing estimated logic status for a sequential circuit containing Plural component circuits, and the method comprises the steps of a) acquiring pieces of status information each representative of a degradation of a failure propagation path in one of the plural component circuits and selectively labeled with indexes to be built in a tree-like index structure so as to indicate a relation of the failure propagation paths from candidates of a failure origin in the sequential circuit to a signal output port of the sequential circuit, one of the indexes given to one of the propagation paths closer to the signal output port serving as an upper level index in the tree-like index structure with respect to other or others of the indexes given to other or others of the propagation paths closer to the candidates and connected to the one of the propagation paths, b) checking the tree-like index structure to see whether one of or ones of the indexes are branched from another of the indexes serving as the upper level index so as to give a tag to the one or ones of the indexes when the one or ones of the indexes are branched from the another of indexes, thereby selectively giving tags to an index or a group of indexes incorporated in the tree-like index structure, c) checking the indexes to see whether or not the tag is shared between more than one of the indexes, and d) determining a logical relation between the more than one of the indexes to be an OR relation when the tag is shared and an AND relation when the tag is not shared.